Joint Routing and Scheduling in Multi%2Dhop Wireless Networks with Directional Antennas.

Exploiting content redundancy for web information extraction.
We propose a novel extraction approach that exploits content redundancy on the web to extract structured data from template-based web sites. We start by populating a seed database with records extracted from a few initial sites. We then identify values within the pages of each new site that match attribute values contained in the seed set of records. To match attribute values with diverse representations across sites, we define a new similarity metric that leverages the templatized structure of attribute content. Specifically, our metric discovers the matching pattern between attribute values from two sites, and uses this to ignore extraneous portions of attribute values when computing similarity scores. Further, to filter out noisy attribute value matches, we exploit the fact that attribute values occur at fixed positions within template-based sites. We develop an efficient Apriori-style algorithm to systematically enumerate attribute position configurations with sufficient matching values across pages. Finally, we conduct an extensive experimental study with real-life web data to demonstrate the effectiveness of our extraction approach. 1.
Exploiting Content Redundancy for Web Information Extraction.
We propose a novel extraction approach that exploits content redundancy on the web to extract structured data from template-based web sites. We start by populating a seed database with records extracted from a few initial sites. We then identify values within the pages of each new site that match attribute values contained in the seed set of records. To match attribute values with diverse representations across sites, we define a new similarity metric that leverages the templatized structure of attribute content. Specifically, our metric discovers the matching pattern between attribute values from two sites, and uses this to ignore extraneous portions of attribute values when computing similarity scores. Further, to filter out noisy attribute value matches, we exploit the fact that attribute values occur at fixed positions within template-based sites. We develop an efficient Apriori-style algorithm to systematically enumerate attribute position configurations with sufficient matching values across pages. Finally, we conduct an extensive experimental study with real-life web data to demonstrate the effectiveness of our extraction approach. 1.
Optimal scheduling for dynamic channel allocation in wireless LANs.

Scalable Content%2DBased Routing in Pub%2FSub Systems.

Multi%2Dquery optimization for sketch%2Dbased estimation.

Internet Research What%27s hot in Search%2C Advertizing%2C and Cloud Computing.

Accelerating Lookups in P2P Systems using Peer Caching.

Efficient Aggregate Computation over Data Streams.

Mining %28Social%29 Network Graphs to Detect Random Link Attacks.

Efficient Constraint Monitoring Using Adaptive Thresholds.
Abstract — Detecting constraint violations in large-scale distributed systems has recently attracted plenty of attention from the research community due to its varied applications (security, network monitoring, etc.). Communication efficiency of these systems is a critical concern and determines their practicality. In this paper, we introduce a new set of methods called non-zero slack schemes to implement distributed SUM queries efficiently. We show, both analytically and empirically, that these methods can lead to a considerable reduction in the amount of communication. We propose three adaptive non-zero slack schemes that adapt to changing data distributions; our best scheme is a lightweight reactive scheme that probabilistically adjusts local constraints based on the occurrence of certain events (using only a periodic probability estimation). We conduct an extensive experimental study using real-life and synthetic data sets, and show that our non-zero slack schemes incur significantly less communication overhead compared to the state of the art zero slack scheme (over a 60 % savings). I.
Detecting Anomalies Using End%2Dto%2DEnd Path Measurements.

A New Channel Assignment Mechanism for Rural Wireless Mesh Networks.
villages gateway node Fig. 1. A rural wireless mesh network. Abstract — In this paper we present a new channel allocation scheme for IEEE 802.11 based mesh networks with point-topoint links, designed for rural areas. Our channel allocation scheme allows continuous full-duplex data transfer on every link in the network. Moreover, we do not require any synchronization across the links as the channel assignment prevents cross link interference. Our approach is simple. We consider any link in the network as made up of two directed edges. To each directed edge at a node, we assign a non-interfering IEEE 802.11 channel so that the set of channels assigned to the outgoing edges is disjoint from channels assigned to the incoming edges. Evaluation of this scheme in a testbed demonstrate throughput gains of between 50 − 100%, and significantly less end-to-end delays, over existing link scheduling/channel allocation protocols (such as 2P [11]) designed for point-to-point mesh networks. Formally speaking, this channel allocation scheme is equivalent to an edge-coloring problem, that we call the Directed Edge Coloring (DEC) problem. We establish a relationship between this coloring problem and the classical vertex coloring problem, and thus, show that this problem is NP-hard. More precisely, we give an algorithm that, given k vertex coloring of a graph can directed edge color it using ξ(k)  � colors, where ξ(k) is the ≥ k. smallest integer n such that � n ⌊n/2⌋ I.
Minimum Cost Topology Construction for Rural Wireless Mesh Networks.
Abstract—IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NPhard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic. I.


Graph summarization with bounded error.
We propose a highly compact two-part representation of a given graph G consisting of a graph summary and a set of corrections. The graph summary is an aggregate graph in which each node corresponds to a set of nodes in G, and each edge represents the edges between all pair of nodes in the two sets. On the other hand, the corrections portion specifies the list of edge-corrections that should be applied to the summary to recreate G. Our representations allow for both lossless and lossy graph compression with bounds on the introduced error. Further, in combination with the MDL principle, they yield highly intuitive coarse-level summaries of the input graph G. We develop algorithms to construct highly compressed graph representations with small sizes and guaranteed accuracy, and validate our approach through an extensive set of experiments with multiple reallife graph data sets. To the best of our knowledge, this is the first work to compute graph summaries using the MDL principle, and use the summaries (along with corrections) to compress graphs with bounded error.
Regular Expression Indexing.
In this paper, we describe the design, architecture, and the lessons learned from the implementation of a fast regular expression indexing engine FREE. FREE uses a prebuilt index to identify the text data units which may contain a matching string and only examines these further. In this way, FREE shows orders of magnitude performance improvement in certain cases over standard regular expression matching systems, such as lex, awk and grep [18, 4].
Efficient Design of End%2Dto%2DEnd Probes for Source%2DRouted Networks.

On Configuring BGP Route Reflectors.
Abstract — The Border Gateway Protocol (BGP) is the standard protocol for exchanging routing information between border routers of Autonomous Systems (ASes) in today’s Internet. Within an AS, border routers exchange externally-learned BGP route advertisements via Internal-BGP (I-BGP) peerings. Naive solutions for these I-BGP peering sessions (e.g., based on full-mesh topologies) simply cannot scale to the sizes of modern AS networks. Carefully designed route-reflector configurations can drastically reduce the total number and connection cost of the required I-BGP sessions. Nevertheless, no principled algorithmic approaches exist for designing such configurations, and current practice relies on manual reflector selection using simple, ad-hoc rules. In this paper, we address the novel and challenging optimization problems involved in designing effective BGP route-reflector configurations for AS networks. More specifically, we consider the problems of selecting route reflectors in an AS topology to minimize: (1) the total connection cost of all I-BGP peering sessions, and (2) the average distance traversed by route advertisements within the AS. We present N P-hardness results that establish the intractability of these problems, and propose several polynomial-time approximation algorithms (based on LP-rounding and combinatorial techniques) with guaranteed (constant-factor or logarithmic) bounds on the quality of the approximate solution. Our simulation results validate our approach, demonstrating the effectiveness of our configuration algorithms over a wide range of network topologies. I.
Optimal Scheduling for Dynamic Channel Allocation in Wireless LANs.

VillageNet A low%2Dcost%2C 802.11%2Dbased mesh network for rural regions.
Abstract — VillageNet is a wireless mesh network that aims to provide low-cost broadband Internet access for rural regions. The cost of building the network is kept low by using off-the-shelf IEEE 802.11 equipment and optimizing the network topology to minimize cost. In this paper we describe the over-all operation of VillageNet and discuss two fundamental problems in building such a network. Nodes in VillageNet communicate using long-distance pointto-point wireless links that are established using high-gain directional antenna. VillageNet uses the 2P MAC protocol [17], that is suited for the interference pattern within such a network. However, the 2P protocol requires the underlying mesh graph (for each 802.11 channel) to be bi-partite. Thus, if K channels are available, then an important consideration is how to select K bi-partite subgraphs to activate, such that the demands of the nodes are best met. We formally pose this problem and present some initial results. Second, we observe that the dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links, and the physical obstructions along those links. Thus to minimize cost, we pose the problem of deciding which links should be established, such that all villages are connected and the cost of constructing antenna towers to establish the selected links is minimized. I.
Streaming Algorithms for Robust%2C Real%2DTime Detection of DDoS Attacks.
Effective mechanisms for detecting and thwarting Distributed Denial-of-Service (DDoS) attacks are becoming in-creasingly important to the success of today’s Internet as a viable commercial and business tool. Most earlier work on the DDoS-detection problem has typically focused on either off-line analyses of DDoS-attack measurements or on techniques targeting a small number of potential victim destinations; unfortunately, such mechanisms are not useful for detecting possible DDoS activity in real time over large ISP networks, where the number of packet destinations to moni-tor can easily rise to several millions. In this paper, we propose novel data-streaming algorithms for the robust, real-time detection of DDoS activity in large ISP networks. The key element of our solution is a new, hash-based synopsis data structure for network-data streams that allows us to efficiently track, in guaranteed small space and time, destination IP addresses in the underlying network that are “large ” with respect to the number of distinct source IP addresses that have established potentially-malicious (e.g., “half-open”) connections to them. Our work is the first to address the problem of efficiently tracking the top distinct-source frequencies over a general stream of updates (insertions and deletions) to the set of underlying network flows, thus enabling us to effectively distinguish between DDoS activity and flash crowds. Preliminary experimental results verify the effectiveness of our approach. Keywords: Data-streaming algorithms, top-k frequencies, denial-of-Service attacks, IP networks, real-time systems.
Streaming Algorithms for Robust%2C Real%2DTime Detection of DDoS Attacks.
Effective mechanisms for detecting and thwarting Distributed Denial-of-Service (DDoS) attacks are becoming in-creasingly important to the success of today’s Internet as a viable commercial and business tool. Most earlier work on the DDoS-detection problem has typically focused on either off-line analyses of DDoS-attack measurements or on techniques targeting a small number of potential victim destinations; unfortunately, such mechanisms are not useful for detecting possible DDoS activity in real time over large ISP networks, where the number of packet destinations to moni-tor can easily rise to several millions. In this paper, we propose novel data-streaming algorithms for the robust, real-time detection of DDoS activity in large ISP networks. The key element of our solution is a new, hash-based synopsis data structure for network-data streams that allows us to efficiently track, in guaranteed small space and time, destination IP addresses in the underlying network that are “large ” with respect to the number of distinct source IP addresses that have established potentially-malicious (e.g., “half-open”) connections to them. Our work is the first to address the problem of efficiently tracking the top distinct-source frequencies over a general stream of updates (insertions and deletions) to the set of underlying network flows, thus enabling us to effectively distinguish between DDoS activity and flash crowds. Preliminary experimental results verify the effectiveness of our approach. Keywords: Data-streaming algorithms, top-k frequencies, denial-of-Service attacks, IP networks, real-time systems.
Efficient Detection of Distributed Constraint Violations.
In many distributed environments, the primary function of monitoring software is to detect anomalies, i.e., instances when system behavior deviates substantially from the norm. In this paper, we propose communication-efficient schemes for the anomaly detection problem, which we model as one of detecting the violation of global constraints defined over distributed system variables. Our approach eliminates the need to continuously track the global system state by decomposing global constraints into local constraints that can be checked efficiently at each site. Only in the occasional event that a local constraint is violated, do we resort to more expensive global constraint checking. We show that the problem of selecting the local constraints, based on frequency distribution of individual system variables, so as to minimize the communication cost is NP-hard. We propose approximation algorithms for computing provably near-optimal (in terms of the number of messages) local constraints. Experimental results with real-life network traffic data sets demonstrate that our technique can reduce message communication overhead by as much as 70 % compared to existing data distribution-agnostic approaches. 1.
Diagnosing Link%2DLevel Anomalies Using Passive Probes.
Abstract—In this paper, we develop passive network tomography techniques for inferring link-level anomalies like excessive loss rates and delay from path-level measurements. Our approach involves placing a few passive monitoring devices on strategic links within the network, and then passively monitoring the performance of network paths that pass through those links. In order to keep the monitoring infrastructure and communication costs low, we focus on minimizing (1) the number of passive probe devices deployed, and (2) the set of monitored paths. For mesh topologies, we show that the above two minimization problems are NP-hard, and consequently, devise polynomialtime greedy algorithms that achieve a logarithmic approximation factor, which is the best possible for any algorithm. We also consider tree topologies typical of Enterprise networks, and show that while similar NP-hardness results hold, constant factor approximation algorithms are possible for such topologies. I.
Routing and Channel Allocation in Rural Wireless Mesh Networks.

VillageNet A low%2Dcost
Abstract — VillageNet is a wireless mesh network that aims to provide low-cost broadband Internet access for rural regions. The cost of building the network is kept low by using off-the-shelf IEEE 802.11 equipment and optimizing the network topology to minimize cost. In this paper we describe the over-all operation of VillageNet and discuss two fundamental problems in building such a network. Nodes in VillageNet communicate using long-distance pointto-point wireless links that are established using high-gain directional antenna. VillageNet uses the 2P MAC protocol [17], that is suited for the interference pattern within such a network. However, the 2P protocol requires the underlying mesh graph (for each 802.11 channel) to be bi-partite. Thus, if K channels are available, then an important consideration is how to select K bi-partite subgraphs to activate, such that the demands of the nodes are best met. We formally pose this problem and present some initial results. Second, we observe that the dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links, and the physical obstructions along those links. Thus to minimize cost, we pose the problem of deciding which links should be established, such that all villages are connected and the cost of constructing antenna towers to establish the selected links is minimized. I.
Monitoring infrastructure for converged networks and services.



Efficient Detection of Distributed Constraint Violations.
In many distributed environments, the primary function of monitoring software is to detect anomalies, i.e., instances when system behavior deviates substantially from the norm. In this paper, we propose communication-efficient schemes for the anomaly detection problem, which we model as one of detecting the violation of global constraints defined over distributed system variables. Our approach eliminates the need to continuously track the global system state by decomposing global constraints into local constraints that can be checked efficiently at each site. Only in the occasional event that a local constraint is violated, do we resort to more expensive global constraint checking. We show that the problem of selecting the local constraints, based on frequency distribution of individual system variables, so as to minimize the communication cost is NP-hard. We propose approximation algorithms for computing provably near-optimal (in terms of the number of messages) local constraints. Experimental results with real-life network traffic data sets demonstrate that our technique can reduce message communication overhead by as much as 70 % compared to existing data distribution-agnostic approaches. 1.
VoIP service quality monitoring using active and passive probes.

Efficient gossip%2Dbased aggregate computation.

Globalization Challenges to Database Community.



Join%2Ddistinct aggregate estimation over update streams.
There is growing interest in algorithms for processing and querying continuous data streams (i.e., data that is seen only once in a fixed order) with limited memory resources. Providing (perhaps approximate) answers to queries over such streams is a crucial requirement for many application environments; examples include large IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed. The ability to estimate the number of distinct (sub)tuples in the result of a join operation correlating two data streams (i.e., the cardinality of a projection with duplicate elimination over a join) is an important requirement for several data-analysis scenarios. For instance, to enable real-time traffic analysis and load balancing, a network-monitoring application may need to estimate the number of distinct (source, destination) IP-address pairs occurring in the stream of IP packets observed by router R1, where the source address is also seen in packets routed through a different router R2. Earlier work has presented solutions to the individual problems of distinct counting and join-size estimation (without duplicate elimination) over streams. These solutions, however, are fundamentally different and extending or combining them to handle our more complex “Join-Distinct ” estimation problem is far from obvious. In this paper, we propose the first space-efficient algorithmic solution to the general Join-Distinct estimation problem over continuous data streams (our techniques can actually handle general update streams comprising tuple deletions as well as insertions). Our estimators are probabilistic in nature and rely on novel algorithms for building and combining a new class of hash-based synopses (termed “JD sketches”) for individual update streams. We demonstrate that our algorithms can provide low error, high-confidence Join-Distinct estimates using only small space and small processing time per update. In fact, we present lower bounds showing that the space usage of our estimators is within small factors of the best possible for the Join-Distinct problem. Preliminary experimental results verify the effectiveness of our approach. 1.
A Cost%2DBased Model and Effective Heuristic for Repairing Constraints by Value Modification.
Data integrated from multiple sources may contain inconsistencies that violate integrity constraints. The constraint repair problem attempts to find “low cost ” changes that, when applied, will cause the constraints to be satisfied. While in most previous work repair cost is stated in terms of tuple insertions and deletions, we follow recent work to define a database repair as a set of value modifications. In this context, we introduce a novel cost framework that allows for the application of techniques from record-linkage to the search for good repairs. We prove that finding minimal-cost repairs in this model is NP-complete in the size of the database, and introduce an approach to heuristic repair-construction based on equivalence classes of attribute values. Following this approach, we define two greedy algorithms. While these simple algorithms take time cubic in the size of the database, we develop optimizations inspired by algorithms for duplicate-record detection that greatly improve scalability. We evaluate our framework and algorithms on synthetic and real data, and show that our proposed optimizations greatly improve performance at little or no cost in repair quality. 1.
Holistic Aggregates in a Networked World Distributed Tracking of Approximate Quantiles.
While traditional database systems optimize for performance on one-shot queries, emerging large-scale monitoring applications require continuous tracking of complex aggregates and data-distribution summaries over collections of physically-distributed streams. Thus, effective solutions have to be simultaneously space efficient (at each remote site), communication efficient (across the underlying communication network), and provide continuous, guaranteedquality estimates. In this paper, we propose novel algorithmic solutions for the problem of continuously tracking complex holistic aggregates in such a distributed-streams setting — our primary focus is on approximate quantile summaries, but our approach is more broadly applicable and can handle other holistic-aggregate functions (e.g., “heavy-hitters ” queries). We present the first known distributed-tracking schemes for maintaining accurate quantile estimates with provable approximation guarantees, while simultaneously optimizing the storage space at each remote site as well as the communication cost across the network. In a nutshell, our algorithms employ a combination of local tracking at remote sites and simple prediction models for local site behavior in order to produce highly communication- and space-efficient solutions. We perform extensive experiments with real and synthetic data to explore the various tradeoffs and understand the role of prediction models in our schemes. The results clearly validate our approach, revealing significant savings over naive solutions as well as our analytical worst-case guarantees. 1.
Query Translation from XPath to SQL in the Presence of Recursive DTDs.
The interaction between recursion in XPATH and  recursion in DTDs makes it challenging to answer  XPATH queries on XML data that is stored in an  RDBMS via schema-based shredding. We present  a new approach to translating XPATH queries into  SQL queries with a simple least fixpoint (LFP) operator,  which is already supported by most commercial   RDBMS. The approach is based on our  algorithm for rewriting XPATH queries into regular   XPATH expressions, which are capable of capturing  both DTD recursion and XPATH queries in  a uniform framework. Furthermore, we provide  an algorithm for translating regular XPATH queries  to SQL queries with LFP, and optimization techniques  for minimizing the use of the LFP operator.
OSS architecture and requirements for VoIP networks.

Algorithms for computing QoS paths with restoration.
There is a growing interest among service providers to offer new services with Quality of Service (QoS) guaranties that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process.
Sketch%2DBased Multi%2Dquery Processing over Data Streams.
Abstract. Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed. Randomized techniques, based on computing small “sketch ” synopses for each stream, have recently been shown to be a very effective tool for approximating the result of a single SQL query over streaming data tuples. In this paper, we investigate the problems arising when data-stream sketches are used to process multiple such queries concurrently. We demonstrate that, in the presence of multiple query expressions, intelligently sharing sketches among concurrent query evaluations can result in substantial improvements in the utilization of the available sketching space and the quality of the resulting approximation error guarantees. We provide necessary and sufficient conditions for multi-query sketch sharing that guarantee the correctness of the result-estimation process. We also prove that optimal sketch sharing typically gives rise to N P-hard questions, and we propose novel heuristic algorithms for finding good sketch-sharing configurations in practice. Results from our experimental study with realistic workloads verify the effectiveness of our approach, clearly demonstrating the benefits of our sketch-sharing methodology. 1
Processing Data%2DStream Join Aggregates Using Skimmed Sketches.
sganguly,minos,rastogi¡ Abstract. There is a growing interest in on-line algorithms for analyzing and querying data streams, that examine each stream element only once and have at their disposal, only a limited amount of memory. Providing (perhaps approximate) answers to aggregate queries over such streams is a crucial requirement for many application environments; examples include large IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed. In this paper, we present the skimmed-sketch algorithm for estimating the join size of two streams. (Our techniques also readily extend to other join-aggregate queries.) To the best of our knowledge, our skimmed-sketch technique is the first comprehensive join-size estimation algorithm to provide tight error guarantees while: (1) achieving the lower bound on the space required by any join-size estimation method in a streaming environment, (2) handling streams containing general update operations (inserts and deletes), (3) incurring a low logarithmic processing time per stream element, and (4) not assuming any a-priori knowledge of the frequency distribution for domain values. Our skimmed-sketch technique achieves all of the above by first skimming the dense frequencies from random hash-sketch summaries of the two streams. It then computes the subjoin size involving only dense frequencies directly, and uses the skimmed sketches only to approximate subjoin sizes for the non-dense frequencies. Results from our experimental study with real-life as well as synthetic data streams indicate that our skimmed-sketch algorithm provides significantly more accurate estimates for join sizes compared to earlier sketch-based techniques. 1
Distributed Set Expression Cardinality Estimation.
We consider the problem of estimating set-expression  cardinality in a distributed streaming environment  where rapid update streams originating at remote sites  are continually transmitted to a central processing system.
WALRUS A Similarity Retrieval Algorithm for Image Databases.

Topology discovery in heterogeneous IP networks the NetInventory system.


Traveling with a Pez Dispenser %28or%2C Routing Issues in MPLS%29.


Algorithms for Computing QoS Paths with Restoration.
There is a growing interest among service providers to offer new services with Quality of Service (QoS) guaranties that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process.
Optimal Configuration for BGP Route Selection.
An Internet Service Provider must provide transit service for traffic between its customers and its providers and, at the same time, attempt to minimize network utilization and balance traffic according to the capacities of its border routers. Central to the selection of border routers for transit traffic flows is the Border Gateway Protocol (BGP) between Autonomous Systems peers, through which route advertisements for network prefixes determine the selection of border routers for each traffic flow.
Physical Topology Discovery for Large Multi%2DSubnet Networks.
Knowledge of the up-to-date physical (i.e., layer-2) topology of an Ethernet network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today&#039;s IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. In this paper, we propose the first complete algorithmic solution for discovering the physical topology of a large, heterogeneous Ethernet network comprising multiple subnets as well as (possibly) dumb or uncooperative network elements. Our algorithms rely on standard SNMP MIB information that is widely supported in modern IP networks and require no modifications to the operating system software running on elements or hosts. Furthermore, we formally demonstrate that our solution is complete for the given MIB data; that is, if the MIB information is sufficient to uniquely identify the network topology then our algorithm is guaranteed to recover it. To the best of our knowledge, ours is the first solution to provide such a strong completeness guarantee.
Robust Monitoring of Link Delays and Faults in IP Networks.
In this paper, we develop failure-resilient techniques for monitoring link delays and faults in a Service Provider or Enterprise IP network. Our two-phased approach attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. In the first phase of our approach, we compute the locations of a minimal set of monitoring stations such that all network links are covered, even in the presence of several link failures. Subsequently, in the second phase, we compute a minimal set of probe messages that are transmitted by the stations to measure link delays and isolate network faults. We show that both the station selection problem as well as the probe assignment problem are NP-hard. We then propose greedy approximation algorithms that achieve a logarithmic approximation factor for the station selection problem and a constant factor for the probe assignment problem. These approximation ratios are provably very close to the best possible bounds for any algorithm.
Processing Set Expressions over Continuous Update Streams.

Capturing both Types and Constraints in Data Integration.
We propose a framework for integrating data from multiple relational sources into an XML document that both conforms to a given DTD and satisfies predefined XML constraints. The framework is based on a specification language, AIG, that extends a DTD by (1) associating element types with semantic attributes (inherited and synthesized, inspired by the corresponding notions from Attribute Grammars), (2) computing these attributes via parameterized SQL queries over multiple data sources, and (3) incorporating XML keys and inclusion constraints. The novelty of AIG consists in semantic attributes and their dependency relations for controlling context-dependent, DTD-directed construction of XML documents, as well as for checking XML constraints in parallel with document-generation. We also present cost-based optimization techniques for efficiently evaluating AIGs, including algorithms for merging queries and for scheduling queries on multiple data sources. This provides a new grammar-based approach for data integration under both syntactic and semantic constraints. 1.
Techniques for Clustering Massive Data Sets.

XTRACT Learning Document Type Descriptors from XML Document Collections.

Building Decision Trees with Constraints.

DTD Inference from XML Documents The XTRACT Approach.
XML is rapidly emerging as the new standard for data representation and exchange on the Web. Document Type Descriptors (DTDs) contain valuable information on the structure of XML documents and thus have a crucial role in the efficient storage and querying of XML data. Despite their importance, however, DTDs are not mandatory, and it is quite possible for documents in XML databases to not have accompanying DTDs. In this paper, we present an overview of XTRACT, a novel system for inferring a DTD schema for a database of XML documents. Since the DTD syntax incorporates the full expressive power of regular expressions, naive approaches typically fail to produce concise and intuitive DTDs. Instead, the XTRACT inference algorithms employ a sequence of sophisticated steps that involve: (1) finding patterns in the input sequences and replacing them with regular expressions to generate &#034;general &#034; candidate DTDs, (2) factoring candidate DTDs using adaptations of algorithms from the logic optimization literature, and (3) applying the Minimum Description Length (MDL) principle to find the best DTD among the candidates.
Scalable Filtering of XML Data for Web Services.
With the advent of XML as the de facto language for data interchange and the rapid emergence of Web services, Web applications have to deal with increasing amounts of XML tra#c, such as SOAP requests. In order to scale to large number of clients and high data tra#c, back-end systems to which Web services are mapped face the challenging task of e#ciently filtering, classifying, and routing incoming XML requests to the appropriate component in the infrastructure. As the destination of each XML request depends on its actual type and content, Web service applications have to incorporate highly-e#cient content-based routing technology. In this paper, we address the issue of scalable filtering of XML data. We describe sophisticated techniques for matching data against large number of tree-structured filters expressed using the XPath language. We propose a hierarchical XML routing architecture that supports extremely high loads, and we present experimental results that demonstrate its performance.
Mining Optimized Gain Rules for Numeric Attributes.
Association rules are useful for determining correlations between attributes of a relation and have applications in marketing, nancial and retail sectors. Furthermore, optimized association rules are an e ective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support, con dence or gain of the rule is maximized. In this paper, we generalize the optimized gain association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving the uninstantiated attribute. For rules containing a single numeric attribute, we present an algorithm with linear complexity for computing optimized gain rules. Furthermore, we propose a bucketing technique that can result in a signi cant reduction in input size by coalescing contiguous values without sacri cing optimality. We also present an approximation algorithm based on dynamic programming for two numeric attributes. Using recent results on binary space partitioning trees, we show that the approximations are within a constant factor of the optimal optimized gain rules. Our experimental results with synthetic data sets for a single numeric attribute demonstrate that our algorithm scales up linearly with the attribute&#039;s domain size as well as the number of disjunctions. In addition, we show that applying our optimized rule framework to a population survey real-life data set enables us to discover interesting underlying correlations among the attributes.
Guest Editor Introduction Special Section on Online Analysis and Querying of Continuous Data Streams.

Detection and Recovery Techniques for Database Corruption.

Optimal configuration of OSPF aggregates.
Abstract—Open Shortest Path First (OSPF) is a popular protocol for routing within an Autonomous System (AS) domain. In order to scale for large networks containing hundreds and thousands of subnets, OSPF supports a two-level hierarchical routing scheme through the use of OSPF areas. Subnet addresses within an area are aggregated, and this aggregation is a crucial requirement for scaling OSPF to large AS domains, as it results in significant reductions in routing table sizes, smaller link-state databases, and less network traffic to synchronize the router link-state databases. On the other hand, address aggregation also implies loss of information about the length of the shortest path to each subnet, which in turn, can lead to suboptimal routing. In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound   on the number of aggregates to be advertised and a weight-assignment function for the aggregates, computes the   aggregates that result in the minimum cumulative error in the shortest path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weightassignment problem can be devised, the general problem itself is¡£ ¢-hard. Consequently, we have to rely on search heuristics to solve the weightassignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios. I.
RE%2Dtree an efficient index structure for regular expressions.
Abstract. Due to their expressive power, regular expressions (REs) are quickly becoming an integral part of language specifications for several important application scenarios. Many of these applications have to manage huge databases of RE specifications and need to provide an effective matching mechanism that, given an input string, quickly identifies the REs in the database that match it. In this paper, we propose the RE-tree, a novel index structure for large databases of RE specifications. Given an input query string, the RE-tree speeds up the retrieval of matching REs by focusing the search and comparing the input string with only a small fraction of REs in the database. Even though the RE-tree is similar in spirit to other tree-based structures that have been proposed for indexing multidimensional data, RE indexing is significantly more challenging since REs typically represent infinite sets of strings with no well-defined notion of spatial locality. To address these new challenges, our RE-tree index structure relies on novel measures for comparing the relative sizes of infinite regular languages. We also propose innovative solutions for the various RE-tree operations including the effective splitting of RE-tree nodes and computing a “tight ” bounding RE for a collection of REs. Finally, we demonstrate how samplingbased approximation algorithms can be used to significantly speed up the performance of RE-tree operations. Preliminary experimental results with moderately large synthetic data sets indicate that the RE-tree is effective in pruning the search space and easily outperforms naive sequential search approaches.


Optimal Configuration of OSPF Aggregates.
Abstract—Open Shortest Path First (OSPF) is a popular protocol for routing within an Autonomous System (AS) domain. In order to scale for large networks containing hundreds and thousands of subnets, OSPF supports a two-level hierarchical routing scheme through the use of OSPF areas. Subnet addresses within an area are aggregated, and this aggregation is a crucial requirement for scaling OSPF to large AS domains, as it results in significant reductions in routing table sizes, smaller link-state databases, and less network traffic to synchronize the router link-state databases. On the other hand, address aggregation also implies loss of information about the length of the shortest path to each subnet, which in turn, can lead to suboptimal routing. In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound   on the number of aggregates to be advertised and a weight-assignment function for the aggregates, computes the   aggregates that result in the minimum cumulative error in the shortest path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weightassignment problem can be devised, the general problem itself is¡£ ¢-hard. Consequently, we have to rely on search heuristics to solve the weightassignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios. I.
Restoration Algorithms for Virtual Private Networks in the Hose Model.
A Virtual Private Network (VPN) aims to emulate the services provided by a private network over the shared Internet. The endpoints of a VPN are connected using abstractions such as Virtual Channels (VCs) of ATM or Label Switching Paths (LSPs) of MPLS technologies. Reliability of an end-to-end VPN connection depends on the reliability of the links and nodes in the fixed path that it traverses in the network. In order to ensure service quality and availability in a VPN, seamless recovery from failures is essential. This work considers the problem of fast recovery in the recently proposed VPN hose model. In the hose model bandwidth is reserved for traffic aggregates instead of pairwise specifications to allow any traffic pattern among the VPN endpoints. This work assumes that the VPN endpoints are connected using a tree structure and at any time, at most one tree link can fail (i.e., single link failure model). A restoration algorithm must select asetofbackup edges and allocate necessary bandwidth on them in advance, so that the traffic disrupted by failure of a primary edge can be re-routed via backup paths. We aim at designing an optimal restoration algorithm to minimize the total bandwidth reserved on the backup edges. This problem is a variant of optimal graph augmentation problem which is NP-Complete. Thus, we present a polynomial-time approximation algorithm that guarantees a solution which is at most 16 times of the optimum. The algorithm is based on designing two reductions to convert the original problem to one of adding minimum cost edges to the VPN tree so that the resulting graph is 2-connected, which can be solved in polynomial time using known algorithms. The two reductions introduce approximation factors of 8 and 2, respectively, thus resulting in a 16-appro...
Network Data Mining and Analysis The NEMESIS Project.
Modern communication networks generate large amounts of operational  data, including traffic and utilization statistics and alarm/fault data at various  levels of detail. These massive collections of network-management data can  grow in the order of several Terabytes per year, and typically hide &#034;knowledge&#034;  that is crucial to some of the key tasks involved in effectively managing a communication  network (e.g., capacity planning and traffic engineering). In this short  paper, we provide an overview of some of our recent and ongoing work in the  context of  the   21501-403  project at Bell Laboratories that aims to develop  novel data warehousing and mining technology for the effective storage, exploration,  and analysis of massive network-management data sets. We first give  some highlights of our work on Model-Based Semantic Compression (MBSC),  a novel data-compression framework that takes advantage of attribute semantics  and data-mining models to perform lossy compression of massive network-data  tables. We discuss the architecture and some of the key algorithms underlying      , a model-based semantic compression system that exploits predictive  data correlations and prescribed error tolerances for individual attributes to  construct concise and accurate Classification and Regression Tree (CaRT) models  for entire columns of a table. We also summarize some of our ongoing work  on warehousing and analyzing network-fault data and discuss our vision of how  data-mining techniques can be employed to help automate and improve faultmanagement  in modern communication networks. More specifically, we describe  the two key components of modern fault-management architectures, namely the  event-correlation and the root-cause analysis engines, and propose the us...
Processing complex aggregate queries over data streams.
Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed.
Querying and mining data streams you only get one look a tutorial.

RE%2DTree An Efficient Index Structure for Regular Expressions.
Abstract. Due to their expressive power, regular expressions (REs) are quickly becoming an integral part of language specifications for several important application scenarios. Many of these applications have to manage huge databases of RE specifications and need to provide an effective matching mechanism that, given an input string, quickly identifies the REs in the database that match it. In this paper, we propose the RE-tree, a novel index structure for large databases of RE specifications. Given an input query string, the RE-tree speeds up the retrieval of matching REs by focusing the search and comparing the input string with only a small fraction of REs in the database. Even though the RE-tree is similar in spirit to other tree-based structures that have been proposed for indexing multidimensional data, RE indexing is significantly more challenging since REs typically represent infinite sets of strings with no well-defined notion of spatial locality. To address these new challenges, our RE-tree index structure relies on novel measures for comparing the relative sizes of infinite regular languages. We also propose innovative solutions for the various RE-tree operations including the effective splitting of RE-tree nodes and computing a “tight ” bounding RE for a collection of REs. Finally, we demonstrate how samplingbased approximation algorithms can be used to significantly speed up the performance of RE-tree operations. Preliminary experimental results with moderately large synthetic data sets indicate that the RE-tree is effective in pruning the search space and easily outperforms naive sequential search approaches.
Tree Pattern Aggregation for Scalable XML Data Dissemination.
With the rapid growth of XML-document traffic on the  Internet, scalable content-based dissemination of XML  documents to a large, dynamic group of consumers has  become an important research challenge. To indicate  the type of content that they are interested in, data  consumers typically specify their subscriptions using  some XML pattern specification language (e.g., XPath).
DTD%2DDirected Publishing with Attribute Translation Grammars.
We present a framework for publishing relational  data in XML with respect to a fixed DTD. In data  exchange on the Web, XML views of relational  data are typically required to conform to a predefined  DTD. The presence of recursion in a DTD as  well as non-determinism makes it challenging to  generate DTD-directed, efficient transformations.
Mining Optimized Association Rules with Categorical and Numeric Attributes.
Association rules are useful for determining correlations between attributes of a relation and have applications in marketing, financial and retail sectors. Furthermore,  optimized association rules are an effective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support or confidence of the rule is maximized. In this paper, we generalize the optimized association rules problem in three ways -- 1) association rules are allowed to contain disjunctions over uninstantiated attributes, 2) association rules are permitted to contain an arbitrary number of uninstantiated attributes, and 3) uninstantiated attributes can be either categorical or numeric. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving multiple attributes. We present effective...
Mining Sequential Patterns with Regular Expression Constraints.
KAIST\Lambda and AITrcy 373-1 Kusong-Dong, Yusong-Gu
Algorithms for provisioning virtual private networks in the hose model.
Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. In this paper, we develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP-hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is O(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Finally, we extend our proposed algorithms for computing VPN trees to the case when network links have capacity constraints. We show that in the presence of link capacity constraints, computing the optimal VPN tree is NP-hard even when ingress and egress bandwidths of each endpoint are equal. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints. 1
SPARTAN using constrained models for guaranteed%2Derror semantic compression.

Efficient filtering of XML documents with XPath expressions.
cychan,pascal,minos,rastogi¡ We propose a novel index structure, termed XTrie, that supports the efficient filtering of XML documents based on XPath expressions. Our XTrie index structure offers several novel features that make it especially attractive for largescale publish/subscribe systems. First, XTrie is designed to support effective filtering based on complex XPath expressions (as opposed to simple, single-path specifications). Second, our XTrie structure and algorithms are designed to support both ordered and unordered matching of XML data. Third, by indexing on sequences of element names organized in a trie structure and using a sophisticated matching algorithm, XTrie is able to both reduce the number of unnecessary index probes as well as avoid redundant matchings, thereby providing extremely efficient filtering. Our experimental results over a wide range of XML document and XPath expression workloads demonstrate that our XTrie index structure outperforms earlier approaches by wide margins. 1.
Data Mining Meets Network Management The NEMESIS Project.
Modern communication networks generate large amounts of operational data, including traffic and utilization statistics and alarm/fault data at various levels of detail. These massive collections of network-management data can grow in the order of several Terabytes per year, and typically hide &#034;knowledge&#034; that is crucial to some of the key tasks involved in effectively managing a communication network (e.g., capacity planning and traffic engineering). In this short paper, we provide an overview of some of our recent and ongoing work in the context of the NEMESIS project at Bell Laboratories that aims to develop novel data warehousing and mining technology for the effective storage, exploration, and analysis of massive network-management data sets. We first give some highlights of our work on Model-Based Semantic Compression (MBSC), a novel data-compression framework that takes advantage of attribute semantics and data-mining models to perform lossy compression of massive network-data tables. We discuss the architecture and some of the key algorithms underlying SPARTAN , a model-based semantic compression system that exploits predictive data correlations and prescribed error tolerances for individual attributes to construct concise and accurate Classification and Regression Tree (CaRT) models for entire columns of a table. We also summarize some of our ongoing work on warehousing and analyzing network-fault data and discuss our vision of how data-mining techniques can be employed to help automate and improve fault-management in modern communication networks. More specifically, we describe the two key components of modern fault-management architectures, namely the event-correlation and the root-cause analysis engines, and propose the use of mining ideas for the automated i...
Traveling with a Pez Dispenser %28Or%2C Routing Issues in MPLS%29.

Efficiently Monitoring Bandwidth and Latency in IP Networks.
Abstract—Effective monitoring of network utilization and performance indicators is a key enabling technology for proactive and reactive resource management, flexible accounting, and intelligent planning in nextgeneration IP networks. In this paper, we address the challenging problem of efficiently monitoring bandwidth utilization and path latencies in an IP data network. Unlike earlier approaches, our measurement architecture assumes a single point-of-control in the network (corresponding to the Network Operations Center) that is responsible for gathering bandwidth and latency information using widely-deployed management tools, like SNMP, RMON/NetFlow, and explicitly-routed IP probe packets. Our goal is to identify effective techniques for monitoring (a) bandwidth usage for a given set of links or packet flows, and (b) path latencies for a given set of paths, while minimizing the overhead imposed by the management tools on the underlying production network. We demonstrate that minimizing overheads under our measurement model gives rise to new combinatorial optimization problems, most of which prove to be N P-hard. We also propose novel approximation algorithms for these optimization problems and prove guaranteed upper bounds on their worst-case performance. Our simulation results validate our approach, demonstrating the effectiveness of our novel monitoring algorithms over a wide range of network topologies. I.
Efficiently Monitoring Bandwidth and Latency in IP Networks.
Abstract—Effective monitoring of network utilization and performance indicators is a key enabling technology for proactive and reactive resource management, flexible accounting, and intelligent planning in nextgeneration IP networks. In this paper, we address the challenging problem of efficiently monitoring bandwidth utilization and path latencies in an IP data network. Unlike earlier approaches, our measurement architecture assumes a single point-of-control in the network (corresponding to the Network Operations Center) that is responsible for gathering bandwidth and latency information using widely-deployed management tools, like SNMP, RMON/NetFlow, and explicitly-routed IP probe packets. Our goal is to identify effective techniques for monitoring (a) bandwidth usage for a given set of links or packet flows, and (b) path latencies for a given set of paths, while minimizing the overhead imposed by the management tools on the underlying production network. We demonstrate that minimizing overheads under our measurement model gives rise to new combinatorial optimization problems, most of which prove to be N P-hard. We also propose novel approximation algorithms for these optimization problems and prove guaranteed upper bounds on their worst-case performance. Our simulation results validate our approach, demonstrating the effectiveness of our novel monitoring algorithms over a wide range of network topologies. I.
Algorithms for provisioning virtual private networks in the hose model.
Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. In this paper, we develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP-hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is O(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Finally, we extend our proposed algorithms for computing VPN trees to the case when network links have capacity constraints. We show that in the presence of link capacity constraints, computing the optimal VPN tree is NP-hard even when ingress and egress bandwidths of each endpoint are equal. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints. 1
Main%2DMemory Index Structures with Fixed%2DSize Partial Keys.

Independence is Good Dependency%2DBased Histogram Synopses for High%2DDimensional Data.
Approximating the joint data distribution of a multi-dimensional data set through a compact and accurate histogram synopsis is a fundamental problem arising in numerous practical scenarios, including query optimization and approximate query answering. Existing solutions either rely on simplistic independence assumptions or try to directly approximate the full joint data distribution over the complete set of attributes. Unfortunately, both approaches are doomed to fail for high-dimensional data sets with complex correlation patterns between attributes. In this paper, we propose a novel approach to histogram-based synopses that employs the solid foundation of statistical interaction models to explicitly identify and exploit the statistical characteristics of the data. Abstractly, our key idea is to break the synopsis into (1) a statistical interaction model that accurately captures significant correlation and independence patterns in data, and (2) a collection of histograms on low-dimensional marginals that, based on the model, can provide accurate approximations of the overall joint data distribution. Extensive experimental results with several real-life data sets verify the effectiveness of our approach. An important aspect of our general, model-based methodology is that it can be used to enhance the performance of other synopsis techniques that are based on data-space partitioning (e.g., wavelets) by providing an effective tool to deal with the “dimensionality curse”. 1.
SPARTAN A Model%2DBased Semantic Compression System for Massive Data Tables.

Provisioning a virtual private network a network design problem for multicommodity flow.
Consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. Virtual private networks (VPNs) are services that support such a construct; rather than building a new physical network on the group of nodes that must be connected, bandwidth in the underlying network is reserved for communication within the group, forming a virtual “sub-network.” Provisioning a virtual private network over a set of terminals gives rise to the following general network design problem. We have bounds on the cumulative amount of traffic each terminal can send and receive; we must choose a path for each pair of terminals, and a bandwidth allocation for each edge of the network, so that any traffic matrix consistent with the given upper bounds can be feasibly routed. Thus, we are seeking to design a network that can support a continuum of possible traffic scenarios. We provide optimal and approximate algorithms for several variants of this problem, depending on whether the traffic matrix is required to be symmetric, and on whether the designed network is required to be a tree (a natural constraint in a number of basic applications). We also establish a relation between this collection of network design problems and a variant of the facility location problem introduced by Karger and Minkoff; we extend their results by providing a stronger approximation algorithm for this latter problem. 1
Using Semantic Knowledge of Distributed Objects to Increase Reliability and Availability.
As systems become more distributed, they also become more complex. To ensure consistent execution while maximizing availability, distributed applications use various mechanisms such as replication, load balancing, and data caching. The protocols used for consistency management and component availability are traditionally instantiated by the application. However, in distributed object-based environments like CORBA or Java RMI, the infrastructure can often determine adequate protocols to guarantee liveness and safety based on the request and semantic knowledge of the application. This paper discusses how semantic knowledge of distributed objects can help implement intelligent behavior in middleware and choose optimal protocols for distributed component interactions.
Overcoming Heterogeneity and Autonomy in Multidatabase Systems.

Cure An Efficient Clustering Algorithm for Large Databases.
Discovering communities from a graph structure such as the Web has become an interesting research problem recently. In this paper, comparing with the state-of-the-art authority detecting and graph partitioning methods, we propose a concentric-circle model to more accurately define communities. With this model, a community could be described as a set of concentric-circles. The most important objects representing the concept of a whole community lie in the center and are called core objects. Affiliated objects, which are related to the core objects, surround the core with different ranks. Base on the concentric-circle model, a novel algorithm is developed to discover communities conforming to this model. We also conducted a case study to automatically discover research interest groups in the computer science domain from the Web. Experiments show that our method is very effective to generate high-quality communities with more clear structure and more tunable granularity.
Mining optimized support rules for numeric attributes.
In this paper, we generalize the optimized support association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. For rules containing a single numeric attribute, we present a dynamic programming algorithm for computing optimized association rules. Furthermore, we propose a bucketing technique for reducing the input size, and a divide and conquer strategy that improves the performance significantly without sacrificing optimality. Our experimental results for a single numeric attribute indicate that our bucketing and divide and conquer enhancements are very effective in reducing the execution times and memory requirements of our dynamic programming algorithm. Furthermore, they show that our algorithms scale up almost linearly with the attribute&#039;s domain size as well as the number of disjunctions.  1 Introduction  Association rules, introduced in [AIS93], provide a useful mechanism for discovering correlations among the underlying data. In it...
Reminiscences on Influential Papers.

Approximate query processing using wavelets.
Abstract. Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today’s decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing
Topology Discovery in Heterogeneous IP Networks.
Abstract — Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today’s IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either (a) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored, or (b) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of a topology discovery tool that has been tested on Lucent’s own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology in time that is roughly quadratic in the number of network elements. I.
Efficient algorithms for constructing decision trees with constraints.
Classification is an important problem in data mining. A number of popular classifiers construct decision trees to generate class models. Frequently, however, the constructed trees are complex with hundreds of nodes and thus difficult to comprehend, a fact that calls into question an oftencited benefit that decision trees are easy to interpret. In this paper, we address the problem of constructing &#034;simple &#034; decision trees with few nodes that are easy for humans to interpret. By permitting users to specify constraints on tree size or accuracy, and then building the &#034;best&#034; tree that satisfies the constraints, we ensure that the final tree is both easy to understand and has good accuracy. We develop novel branch-and-bound algorithms for pushing the constraints into the building phase of classifiers, and pruning early tree nodes that cannot possibly satisfy the constraints. Our experimental results with real-life and synthetic data sets demonstrate that significant performance speedups and...
XTRACT A System for Extracting Document Type Descriptors from XML Documents.

Efficient Algorithms for Mining Outliers from Large Data Sets.
In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its k  th  nearest neighbor. We rank each point on the basis of its distance to its k  th  nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nestedloop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.  1 
On%2Dline Reorganization in Object Databases.

Approximate Query Processing Using Wavelets.
Abstract. Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today’s decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing
PUBLIC A Decision Tree Classifier that Integrates Building and Pruning.
Classification is an important problem in data mining. Given a database of records, each with  a class label, a classifier generates a concise and meaningful description for each class that can be  used to classify subsequent records. A number of popular classifiers construct decision trees to  generate class models. These classifiers first build a decision tree and then prune subtrees from  the decision tree in a subsequent pruning phase to improve accuracy and prevent &#034;overfitting&#034;.  Generating the decision tree in two distinct phases could result in a substantial amount  of wasted effort since an entire subtree constructed in the first phase may later be pruned in  the next phase. In this paper, we propose PUBLIC, an improved decision tree classifier that  integrates the second &#034;pruning&#034; phase with the initial &#034;building&#034; phase. In PUBLIC, a node  is not expanded during the building phase, if it is determined that it will be pruned during  the subsequent pruning phase. In order to ma...
ROCK A Robust Clustering Algorithm for Categorical Attributes.
Clustering, in data mining, is useful to discover distribution patterns in the underlying data. Clustering algorithms usually employ a distance metric based (e.g., euclidean) similarity measure in order to partition the database such that data points in the same partition are more similar than points in different partitions. In this paper, we study clustering algorithms for data with boolean and categorical attributes. We show that traditional clustering algorithms that use distances between points for clustering are not appropriate for boolean and categorical attributes. Instead, we propose a novel concept of links to measure the similarity/proximity between a pair of data points. We develop a robust hierarchical clustering algorithm ROCK that employs links and not distances when merging clusters.
Improving Predictability of Transaction Execution Times in Real%2Dtime Databases.

Workshop Report 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.

Scalable Data Mining with Model Constraints.

Mining Optimized Support Rules for Numeric Attributes.
In this paper, we generalize the optimized support association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. For rules containing a single numeric attribute, we present a dynamic programming algorithm for computing optimized association rules. Furthermore, we propose a bucketing technique for reducing the input size, and a divide and conquer strategy that improves the performance significantly without sacrificing optimality. Our experimental results for a single numeric attribute indicate that our bucketing and divide and conquer enhancements are very effective in reducing the execution times and memory requirements of our dynamic programming algorithm. Furthermore, they show that our algorithms scale up almost linearly with the attribute&#039;s domain size as well as the number of disjunctions.  1 Introduction  Association rules, introduced in [AIS93], provide a useful mechanism for discovering correlations among the underlying data. In it...
Using Codewords to Protect Database Data from a Class of Software Errors.
Increasingly, for extensibility and performance, specialpurpose application code is being integrated with database system code. Such application code has direct access to database system buffers, and as a result, the danger of data being corrupted due to inadvertent application writes is increased. Previously proposed hardware techniques to protect from corruption require system calls, and their performance depends on details of the hardware architecture. We investigate an alternative approach which uses codewords associated with regions of data to detect corruption and to prevent corrupted data from being used by subsequent transactions. We develop several such techniques which vary in the level of protection, space overhead, performance, and impact on concurrency. These techniques are implemented in the Dalí main-memory storage manager, and the performance impact of each on normal processing is evaluated. Novel techniques are developed to recover when a transaction had read corrupted data caused by a bad write, and gone on to write other data in the database. These techniques use limited and relatively low-cost logging of transaction reads to trace the corruption, and may also prove useful when resolving problems caused by incorrect data entry and other logical errors. 1.
ROCK A Robust Clustering Algorithm for Categorical Attributes.
Clustering, in data mining, is useful to discover distribution patterns in the underlying data. Clustering algorithms usually employ a distance metric based (e.g., euclidean) similarity measure in order to partition the database such that data points in the same partition are more similar than points in different partitions. In this paper, we study clustering algorithms for data with boolean and categorical attributes. We show that traditional clustering algorithms that use distances between points for clustering are not appropriate for boolean and categorical attributes. Instead, we propose a novel concept of links to measure the similarity/proximity between a pair of data points. We develop a robust hierarchical clustering algorithm ROCK that employs links and not distances when merging clusters.
Scheduling and Data Replication to Improve Tape Jukebox Performance.

Mining Optimized Gain Rules for Numeric Attributes.
Association rules are useful for determining correlations between attributes of a relation and have applications in marketing, nancial and retail sectors. Furthermore, optimized association rules are an e ective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support, con dence or gain of the rule is maximized. In this paper, we generalize the optimized gain association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving the uninstantiated attribute. For rules containing a single numeric attribute, we present an algorithm with linear complexity for computing optimized gain rules. Furthermore, we propose a bucketing technique that can result in a signi cant reduction in input size by coalescing contiguous values without sacri cing optimality. We also present an approximation algorithm based on dynamic programming for two numeric attributes. Using recent results on binary space partitioning trees, we show that the approximations are within a constant factor of the optimal optimized gain rules. Our experimental results with synthetic data sets for a single numeric attribute demonstrate that our algorithm scales up linearly with the attribute&#039;s domain size as well as the number of disjunctions. In addition, we show that applying our optimized rule framework to a population survey real-life data set enables us to discover interesting underlying correlations among the attributes.
Scalable Algorithms for Mining Large Databases.
Methods for efficient mining of frequent patterns have been studied extensively by many researchers. However, the previously proposed methods still encounter some performance bottlenecks when mining databases with different data characteristics, such as dense vs. sparse, long vs. short patterns, memory-based vs. disk-based, etc.
WALRUS A Similarity Retrieval Algorithm for Image Databases.

Of Crawlers%2C Portals%2C Mice and Men Is there more to Mining the Web%3F %28Panel%29.

DataBlitz Storage Manager Main Memory Database Performance for Critical Applications.
General-purpose commercial disk-based database systems, though widely employed in practice, have failed to meet the performance requirements of applications requiring short, predictable response times, and extremely
Update Propagation Protocols For Replicated Databases.

SPIRIT Sequential Pattern Mining with Regular Expression Constraints.
Discovering sequential patterns is an important problem in  data mining with a host of application domains including  medicine, telecommunications, and the World Wide Web. Conventional
SPIRIT Sequential Pattern Mining with Regular Expression Constraints.
Discovering sequential patterns is an important problem in  data mining with a host of application domains including  medicine, telecommunications, and the World Wide Web. Conventional
Data Mining and the Web Past%2C Present and Future.

Mining Optimized Association Rules with Categorical and Numeric Attributes.
Association rules are useful for determining correlations between attributes of a relation and have applications in marketing, financial and retail sectors. Furthermore,  optimized association rules are an effective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support or confidence of the rule is maximized. In this paper, we generalize the optimized association rules problem in three ways -- 1) association rules are allowed to contain disjunctions over uninstantiated attributes, 2) association rules are permitted to contain an arbitrary number of uninstantiated attributes, and 3) uninstantiated attributes can be either categorical or numeric. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving multiple attributes. We present effective...
CURE An Efficient Clustering Algorithm for Large Databases.
Discovering communities from a graph structure such as the Web has become an interesting research problem recently. In this paper, comparing with the state-of-the-art authority detecting and graph partitioning methods, we propose a concentric-circle model to more accurately define communities. With this model, a community could be described as a set of concentric-circles. The most important objects representing the concept of a whole community lie in the center and are called core objects. Affiliated objects, which are related to the core objects, surround the core with different ranks. Base on the concentric-circle model, a novel algorithm is developed to discover communities conforming to this model. We also conducted a case study to automatically discover research interest groups in the computer science domain from the Web. Experiments show that our method is very effective to generate high-quality communities with more clear structure and more tunable granularity.
PUBLIC A Decision Tree Classifier that Integrates Building and Pruning.
Classification is an important problem in data mining. Given a database of records, each with  a class label, a classifier generates a concise and meaningful description for each class that can be  used to classify subsequent records. A number of popular classifiers construct decision trees to  generate class models. These classifiers first build a decision tree and then prune subtrees from  the decision tree in a subsequent pruning phase to improve accuracy and prevent &#034;overfitting&#034;.  Generating the decision tree in two distinct phases could result in a substantial amount  of wasted effort since an entire subtree constructed in the first phase may later be pruned in  the next phase. In this paper, we propose PUBLIC, an improved decision tree classifier that  integrates the second &#034;pruning&#034; phase with the initial &#034;building&#034; phase. In PUBLIC, a node  is not expanded during the building phase, if it is determined that it will be pruned during  the subsequent pruning phase. In order to ma...
DataBlitz A High Performance Main%2DMemory Storage Manager.

Ensuring Consistency in Multidatabases by Preserving Two%2DLevel Serializability.
The concept of serializability has been the traditionally accepted correctness criterion in database systems. However, in multidatabase systems (MDBSs), ensuring global serializability is a di cult task. The di culty arises due to the heterogeneity of the concurrency control protocols used by the participating local database management systems (DBMSs), and the desire to preserve the autonomy of the local DBMSs. In general, solutions to the global serializability problem result in executions with a low degree of concurrency. The alternative, relaxed serializability, may result in data inconsistency. In this paper, we introduce a systematic approach to relaxing the serializability requirement in MDBS environments. Our approach exploits the structure of the integrity constraints and the nature of transaction programs to ensure consistency without requiring executions to be serializable. We develop a simple yet powerful classi cation of MDBSs based on the nature of integrity constraints and transaction programs. For each oftheidenti ed models we showhow consistency can be preserved by ensuring that executions are two-level serializable (2LSR). 2LSR is a correctness criterion for MDBS environments weaker than serializability. What makes our approach interesting is that unlike global serializability, ensuring 2LSR in MDBS environments is relatively simple and protocols to ensure 2LSR permit a high degree of concurrency. Furthermore,we believe the range of models we consider cover many practical MDBS environments to which the results of this paper can be applied to preserve database consistency.
Distributed Multi%2DLevel Recovery in Main%2DMemory Databases.

On Correctness of Nonserializable Executions.

Periodic Retrieval of Videos from Disk Arrays.

Multimedia Support for Databases.

Logical and Physical Versioning in Main Memory Databases.
We present a design for multi-version concurrency control and recovery in a main memory database, and describe logical and physical versioning schemes that allow read-only transactions to execute without obtaining data item locks or system latches. These schemes enable a system to guarantee that updaters will never interfere with read-only transactions, and that read-only transactions will not be delayed as long as the operating system provides them with sufficient cycles. Our contributions include several space saving techniques for the main memory implementation. We extend the T-tree index structure (designed for main-memory databases) to support concurrent access and latch-free traversals, and demonstrate the performance benefits of our extensions. Some of these schemes have been implemented on a widely-used software platform within Bell Labs., and the full scheme is implemented in the Dal&#039;i main memory storage manager.  1 Introduction  While disk-based databases exhibit improved pe...
The Architecture of the Dal%ED Main%2DMemory Storage Manager.
ion  Dal&#039;s architecture, illustrated in Figure 2, is organized in multiple layers of abstraction to support the toolkit approach discussed earlier. At the highest level, users can interact with Dal&#039;s relational manager. Below that level is what we call the heap-file/indexing layer, which provides support for fixed-length and variable-length collections, as well as template-based Locks  Logs  System  database  Database  file 1  Database  file 2  Database  file N  Process 1  user code  Dal library  Virtual memory  of process 1  Virtual memory  of process 2  System physical  memory  Process 2  user code  Dal library  Log of  updates to  database  Checkpoint  images of  database  Figure 1.  Architecture of the Dal system.  Bell LabsTechnical Journal uWinter 1997 39 indexing abstractions. In general, at this level, a user does not need to interact with individual locks or latches. (A latchis a short-term lock implemented by a high-speed mutual exclusion mechanism.) Instead, the user specifi...
Architecture Issues In Multimedia Storage Systems.

Fine%2Dgranularity Locking and Client%2DBased Logging for Distributed Architectures.
We present algorithms for fine-granularity locking and client-based logging where all transactional facilities in a distributed client-server architecture are provided locally. Multiple clients are allowed to concurrently modify different objects on the same page without synchronizing their updates. Each client has its own log disk where all log records for updates to locally cached data are written. Transaction rollback and client crash recovery are handled exclusively by the clients and local logs are not merged at any time. Clients can take checkpoints independently, and client clocks do not have to be synchronized.
Client%2DBased Logging for High Performance Distributed Architectures.
In this paper, we propose logging and recovery algorithms for distributed architectures that use local disk space to provide transactional facilities locally. Each node has its own log file where all log records for updates to locally cached pages are written. Transaction rollback and node crash recovery are handled exclusively by each node and log files are not merged at any time. Our algorithms do not require any form of time synchronization between nodes and nodes can take checkpoints independently of each other. Finally, our algorithms make possible a new paradigm for distributed transaction management that has the potential to exploit all available resources and improve scalability and performance.  1 Introduction  The proliferation of inexpensive workstations and networks has created a new era in distributed computing. At the same time, non-traditional applications such as computer aided design (CAD), computer aided software engineering (CASE), geographic information systems (GIS...
Buffer Replacement Algorithms for Multimedia Storage Systems.

Disk Striping in Video Server Environments.

Distributed Multi%2DLevel Recovery in Main%2DMemory Databases.

Fault%2Dtolerant Architectures for Continuous Media Servers.
Continuous media servers that provide support for the storage and retrieval of continuous media data (e.g., video, audio) at guaranteed rates are becoming increasingly important. Such servers, typically, rely on several disks to service a large number of clients, and are thus highly susceptible to disk failures. We have developed two fault-tolerant approaches that rely on admission control in order to meet rate guarantees for continuous media requests. The schemes enable data to be retrieved from disks at the required rate even if a certain disk were to fail. For both approaches, we present data placement strategies and admission control algorithms. We also present design techniques for maximizing the number of clients that can be supported by a continuous media server. Finally, through extensive simulations, we demonstrate the effectiveness of our schemes. 1 Introduction  Rapid advances in computing and communication technologies have fueled an explosive growth in the multimedia indus...
The Storage and Retrieval of Continuous Media Data.
Continuous media applications, which require a guaranteed transfer rate of the data, are becoming an integral part of daily computational life. However, conventional le systems do not provide rate guarantees, and are therefore not suitable for the storage and retrieval of continuous media data (e.g., audio, video). To meet the demands of these new applications, continuous media le systems, which provide rate guarantees by managing critical storage resources such as memory and disks, must be designed. In this paper, we highlight the issues in the storage and retrieval of continuous media data. We rst present a simple scheme for concurrently retrieving multiple continuous media streams from disks. We then introduce a a clever allocation technique for storing continuous media data that eliminates disk latency and thus, drastically reduces RAM requirements. We present, for video data, schemes for implementing the operations fast-forward, rewind and pause. Finally, we conclude by outlining directions for future research in the storage and retrieval of continuous media data. 
A Framework for the Storage and Retrieval of Continous Media Data.

On the Design of a Low%2DCost Video%2Don%2DDemand Storage System.
Recent advances in storage technology, coupled with the dramatic increase in the bandwidth of networks, make it now possible to provide &#034;video on demand&#034; service to viewers. A video on demand server is a computer system that stores videos in compressed digital form and provides support for different portions of compressed video data to be accessed and transmitted concurrently. In this paper, we present a low-cost storage architecture for a video on demand server that relies principally on disks. The high bandwidths of disks in conjunction with a clever strategy for striping videos on them is utilized in order to enable simultaneous access and transmission of different portions of a video, separated by fixed time intervals. We also present a wide range of schemes for implementing VCR-like functions including fast-forward, rewind and pause. Finally, we extend our schemes to the case when videos have different rate requirements. 
Exploiting Transaction Semantics in Multidatabase Systems.
Serializability is the traditionally accepted notion of correctness in most database systems. However,  in a multidatabase system (MDBS) environment consisting of pre-existing and autonomous  database systems, requiring schedules to be serializable could severely hurt performance. Besides,  in a number of instances, the semantics of transactions can be exploited in order to permit certain  non-serializable executions. In this paper, we propose a powerful, yet simple mechanism for specifying,  in an MDBS environment, the set of non-serializable executions that are unacceptable. The  undesirable interleavings among transactions are specified using regular expressions over transaction  types. The mechanism facilitates the development of efficient graph-based schemes for ensuring  that the concurrent execution of transactions in the MDBS environment meet the specifications.  We examine the trade-off between the complexities and the degree of concurrency permitted by the  various schemes. F...
A Framework for the Storage and Retrieval of Continous Media Data.



Research Issues in Multimedia Storage Servers.
this paper, we discuss some of the major research problems that we are working on as part of the Fellini multimedia storage server project at AT&amp;T Bell Labs.  2 Disk Storage Issues
Disk Striping in Video Server Environments.

A Disk%2DBased Storage Architecture for Movie on Demand Servers.
Recent advances in storage technology provides an effective way to store video in digital and compressed form. This, coupled with the recent dramatic increase in the bandwidth of networks, make it possible now to provide to viewers &#034;movies on demand&#034;, thereby eliminating the inflexibility inherent in todays broadcast cable systems. A movie on demand (MOD) server is a computer system that stores movies in compressed digital form and provides support for different portions of compressed movie data to be accessed and transmitted concurrently. Such a server not only enables viewers to watch a movie at any time they desire, but also enables them to apply VCR operations like pause, resume, fast-forward and rewind to the movies they are currently watching. In this paper, we present a disk-based storage architecture for a MOD server. We present a clever strategy for striping movies that enables simultaneous access and transmission of different portions of a movie. We also present a wide range of schemes for implementing VCR-like functions including fast-forward, rewind and pause.
Enhancing Pre%2Dexisting Data Managers with Atomicity and Durability.

On the Storage and Retrieval of Continuous Media Data.
Continuous media applications, which require a guaranteed transfer rate of the data, are becoming an integral part of daily computational life. However, conventional le systems do not provide rate guarantees, and are therefore not suitable for the storage and retrieval of continuous media data (e.g., audio, video). To meet the demands of these new applications, continuous media le systems, which provide rate guarantees by managing critical storage resources such as memory and disks, must be designed. In this paper, we highlight the issues in the storage and retrieval of continuous media data. We rst present a simple scheme for concurrently retrieving multiple continuous media streams from disks. We then introduce a a clever allocation technique for storing continuous media data that eliminates disk latency and thus, drastically reduces RAM requirements. We present, for video data, schemes for implementing the operations fast-forward, rewind and pause. Finally, we conclude by outlining directions for future research in the storage and retrieval of continuous media data. 
Dal%ED A High Performance Main Memory Storage Manager.
Performance needs of many database appli-cations dictate that the entire database be stored in main memory. The Dali system is a main memory storage manager designed to provide the persistence, availability and safety guarantees one typically expects from a disk-resident database, while at the same time pro-viding very high performance by virtue of be-ing tuned to support in-memory data. Dali follows the philosophy of treating all data, in-cluding system data, uniformly as database files that can be memory mapped and directly accessed/updated by user processes. Direct access provides high performance; slower, but more secure, access is also provided through the use of a server process. Various features of Dali can be tailored to the needs of an ap-plication to achieve high performance- for example, concurrency control and logging can be turned off if not desired, which enables Dali to efficiently support applications that re-quire non-persistent memory resident data to be shared by multiple processes. Both object-oriented and relational databases can be im-plemented on top of Dali. Permisrion io copy wiihoui fee all OT pari of this material ir granied provided thai the copies are not made 01 diriribuied for direci cornmenial advantage, the VLDB copyright notice and the title of the publication and ii8 dale appeur, and notice ia given thaf copying ir by pennirrion of the Very Large Data Bare Endowment. To copy otherwire, or to republish, requires a fee and/or special pennirrion from the Endowment.
A Low%2DCost Storage Server for Movie on Demand Databases.
With recent advances in storage and network technology it is now possible to provide movie on demand (MOD) service, eliminating the inflexibility inherent in todays broadcast cable systems. A MOD server is a computer system that stores movies in compressed digital form and provides support for different portions of compressed movie data to be accessed and transmitted concurrently. In this paper, we present a low-cost storage architecture for a MOD server that relies principally on disks. The high bandwidths of disks in conjunction with a clever strategy for striping movies on them is utilized in order to enable simultaneous access and transmission of &#034;certain&#034; different portions of a movie. We also present a wide range of schemes for implementing VCR-like functions.
Efficient Global Transaction Management in Multidatabase Systems.



On Correctness of Non%2Dserializable Executions.
In a number of application environments (e.g., computer aided design), serializability, the traditionally accepted notion of correctness has been found to be too restrictive, and a number of alternate criteria have been proposed in the literature. One such criterion is predicate-wise serializability  (PWSR), which requires only restrictions of schedules that access subsets of the database over which integrity constraints are defined, to be serializable. In this paper, we identify restrictions on the structure of transaction programs, their concurrent execution and their access characteristics under which PWSR schedules preserve database consistency. 
Transcending the Serializability Requirement.
In many real world applications (even in banking), imprecise data is a matter of fact. However, classic database management systems provide little if any help in the management of imprecise data. We are applying methods from interval arithmetic, epsilon serializability, and other related areas to help the application designers in the management of naturally imprecise data. Our approach includes operators on imprecise data that give bounds on the result imprecision and algorithms that constrain the imprecision propagation in the database. 1 Introduction  Traditional database management systems provide support only for precise data, though in the physical world data is often imprecise. An important class of examples is the scientific data such as incomplete recording of data, instrument noise, measurement error, computational model imprecision, and data aggregation of one kind or another. Another example is the &#034;fuzzy&#034; data managed by Epsilon Serializability algorithms [PL91, DP93]. In t...
A Transaction Model for Multidatabase Systems.
a quarterly bulletin of the
Ensuring Transaction Atomicity in Multidatabase Systems.

Relaxing Serializability in Multidatabase Systems.

The Concurrency Control Problem in Multidatabases Characteristics and Solutions.
4: If site s k follows the 2PL protocol, then any function that maps every transaction  T i 2  k to one of its operations that executes between the time T i obtains its last lock and the time it releases its first lock, is a serialization function for s k .  Proof: Let ser be a function that maps every transaction T i 2  k to one of its operations that executes between the time T i obtains its last lock and the time it releases its first lock. We need to show that for any pair of transactions T i ; T j 2  k , if T i is serialized before T j in S k , then ser(T i ) OE&lt;F4.608
Non%2DSerializable Executions in Heterogeneous Distributed Database Systems.

